<?php
/**
 * @title 309. 最佳买卖股票时机含冷冻期 - 增量计算
 * @author start2004
 */


class Solution {

    /**
     * @param Integer[] $prices
     * @return Integer
     */
    function maxProfit($prices) {
        /**
         * @since 2020-07-10 排除特殊情况
         */
        $len = count($prices);
        if($len<=1){
            return 0;
        } else {}

        /**
         * @since 2020-07-10 每次递归结果缓存起来, 避免反复计算
         */
        $dp = [
            -2 => 0,
            -1 => 0,
            0 => 0,
        ];

        /**
         * @since 2020-07-10 公共部分
         */
        $sells = [
            0 => 0-$prices[0],
        ];

        /**
         * @since 2020-07-10 循环计算dp(1)到dp(len-1)
         */
        for($i=1; $i<$len; $i++){
            /**
             * @since 2020-07-10 sell(i)=max(sell(i−1),dp(i−3)−price[i−1])
             */
            $sells[$i] = max($sells[$i-1], $dp[$i-3]-$prices[$i-1]);

            /**
             * @since 2020-08-06 dp(i)=max(dp(i−1),price[i]+sell(i))
             */
            $dp[$i] = max($dp[$i-1], $prices[$i]+$sells[$i]);
        }

        /**
         * @return
         */
        return $dp[$len-1];
    }
}




/**
 * @url http://127.0.0.1/leetcode/202007/2020.07.10_3.php
 */
$datas = [
    [1,2,3,0,2],
    [0,3,8,6,8,6,6,8,2,0,2,7],
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    var_dump($data);

    $obj = new Solution();
    $result = $obj->maxProfit($data);
    var_dump($result);
    echo str_repeat("<br>", 3);
}
$xhprof->end();
